package com.seatiger.structure.queue;

import java.util.PriorityQueue;
import java.util.TreeMap;

/**
 * https://leetcode.cn/problems/top-k-frequent-elements/
 */
public class LC_347 {

    class Freq implements Comparable<Freq>{
        public int e,freq;

        public Freq(int e,int freq) {
            this.e = e;
            this.freq = freq;
        }

        @Override
        public int compareTo(Freq freq) {
            if (this.freq > freq.freq) {
                return 1;
            }else if(this.freq < freq.freq) {
                return -1;
            }
            return 0;
        }
    }

    public int[] topKFrequent(int[] nums, int k) {
        TreeMap<Integer, Integer> map = new TreeMap<>();
        for (int num : nums) {
            if (map.containsKey(num)) {
                map.put(num,map.get(num) + 1);
            }else {
                map.put(num,1);
            }
        }
        //java中的优先队列，底层是一个最小堆
        //保证队首的位置是频率最低的那个值
        PriorityQueue<Freq> queue = new PriorityQueue();
        for (int key : map.keySet()) {
            if (queue.size() < k) {
                //入队
                queue.add(new Freq(key,map.get(key)));
            }else if (map.get(key) > queue.peek().freq) {
                //如果新值的频率比队首的高，那么替换新值
                queue.remove();
                queue.add(new Freq(key,map.get(key)));
            }
        }
        int[] res = new int[queue.size()];
        int index = 0;
        while (!queue.isEmpty()) {
            res[index++] = queue.remove().e;
        }
        return res;
    }
}
